Session 1 : Exercises

We consider a graph consisting of m parallel edges from s to t. Each edge is equipped with a (affine linear) non-negative cost function (Subscript[c, e])((Subscript[x, e])).

A Wardrop Equilibrium is a s-t-Flow such that (Subscript[c, P])((Subscript[x, P]))≤(Subscript[c, Q])((Subscript[x, Q]))for all s-t-paths P and Q with (Subscript[x, P])>0. This means, every path with a positive amount of flow must have the same, minimal cost. Unused paths (with (Subscript[x, P])=0) can have higher cost.
In this simple setting, this means we search flow values (Subscript[x, 1]),...,(Subscript[x, m])≥0 such that ∑(Subscript[x, i])=r (where r is some given demand rate) such that (Subscript[c, i])((Subscript[x, i]))=(min_j)(Subscript[c, j])((Subscript[x, j])) whenever (Subscript[x, i])>0.

Exercise 1

Consider a simple example of two parallel links with cost functions (Subscript[c, 1])(x)=(x^2) and (Subscript[c, 2])(x)=x+1.
Define these two functions.
Define a function, that a vector of flow values (i.e. a list {x1, x2}) and outputs a vector of costs on the edges induced by the above cost functions.
Define a function that checks whether the input flow vector is a Wardrop Equilibrium wrt. to the above cost functions. Hint: Use If and && and || or the AND and OR function.

c1[x_](* .... *)
c2[x_](* .... *)
cost[x_](* .... *)
isequilibrium[x_]

Solution

c1[x_]:=x^2
c2[x_]:=x+1
cost[x_]:={c1[x[[1]]],c2[x[[2]]]}
isequilibrium[x_]:=If[ (x[[1]]==0 || cost[x][[1]]==Min[cost[x]]) && ( x[[2]] == 0 || cost[x][[2]]==Min[cost[x]]),
Print[x," is a Wardrop Equilibrium with cost ", cost[x]],
Print[x," is not a Wardrop Equilibrium (Cost ", cost[x], ")"]]
(* Tests for diffent flows *)
cost[{2,3}]
isequilibrium[{2,3}]
(* Tests for diffent flows *)
cost[{1,0}]
isequilibrium[{1,0}]
(* Tests for diffent flows *)
cost[{2,2}]
isequilibrium[{2,2}]

Exercise 2

Now consider m edges with affine cost functions (Subscript[c, i])(x)=(Subscript[a, i])x+(Subscript[b, i]). Assume that the coefficients of these functions are given as lists a and b. Write functions similar to Exercise 1 for this case.
Hint: To check the equilibrium conditions, you may first create a list using Table[] or Array[] containing for every edge TRUE if the edge satisfies the WE conditions (i.e., if (Subscript[x, e])=0 or (Subscript[c, e])((Subscript[x, e]))=(min_j) (Subscript[c, j])((Subscript[x, j]))). Then you can use the AND function and apply it to the list (using Apply[And, (list)] or And@@list).

(* Example coefficients given as lists *)
a={1,2,1,3};
b={0,1,3,2};
(* Determine number of edges depending on number of coefficients given *)
m=Length[a];
(* Wanted Functions -- the cost functions depend on the index of the edge e and the flow x *)
c[e_,x_](* .... *)
cost[x_](* .... *)
isequilibrium[x_]

Solution

(* Example coefficients given as lists *)
a={1,2,1,3};
b={0,1,3,2};
(* Determine number of edges depending on number of coefficients given *)
m=Length[a];
(* Wanted Functions *)
c[e_,x_]:=a[[e]]*x+b[[e]]
cost[x_]:=Table[ c[e,x[[e]]],{e,1,m}]

isequilibrium[x_]:=If[And@@Table[(x[[e]]==0||cost[x][[e]]==Min[cost[x]]),{e,1,m}],
Print[x," is a WE with costs ",cost[x]],
Print[x," is not a WE (costs ",cost[x], ")"]];

(* Tests *)
isequilibrium[{1,0,0,0}]
isequilibrium[{3,1,0,1/3}]
isequilibrium[{1,2,3,0}]

Exercise 3

Given cost functions (Subscript[c, e])(x) the modified cost functions (Subscript[(OverTilde[c]), e])(x):=(Subscript[c, e])(x)+x (Subscript[c', e])(x) are called marginal cost functions. A Wardrop equilibrium with respect to the marginal cost is a optimal flow, i.e., a flow that minimizes the total cost (∑_e)(Subscript[x, e])(Subscript[c, e])((Subscript[x, e])). 
Assume given cost functions c[e_, x_]. Define a function cmarg[e_, x_] that computes the marginal cost of edge e at x using c[e_, x_e]. 
Hint: You can use the function D[ f , x ] that computes the derivative of the expression f wrt to x. Given a function f, you can create the derivative function as follows g[x_]:= ( D[f[y], y] ) /.y->x. (This computes the derivative of f[y] wrt to y and then plugs in the function argument x for y. See also rules in the next session).
Further, define a function, that given a flow x computes the total cost of that flow. (Use the cost function from Ex. 2 and the function Total).

cmarg[e_,x_](* ... *)
totalcost[x_]

Solution

cmarg[e_,x_]:=c[e,x]+x[[e]]*(D[c[e,ξ],ξ]/.ξ->x)
totalcost[x_]:=Total[cost[x]]